package problems.daily.y2022m7;

import java.util.*;

/**
 * @author habitplus
 * @since 2022/7/23 23:16
 **/
public class Test {

    public static void main(String[] args) {

    }

    class NumberContainers {
        private Map<Integer, PriorityQueue<Integer>> indexMap;
        private Map<Integer, Integer> map;

        public NumberContainers() {
            indexMap = new HashMap<>();
            map = new HashMap<>();
        }

        public void change(int index, int number) {
            Integer num = map.getOrDefault(index, null);
            if (num == null) {
                // 当前位置没有数
                map.put(index, number);
                PriorityQueue<Integer> pq = indexMap.getOrDefault(number, null);
                if (pq == null) {
                    pq = new PriorityQueue<>(Integer::compareTo);
                    pq.add(index);
                    indexMap.put(number, pq);
                } else {
                    pq.add(index);
                }
            } else if (num != number) {
                // 当前位置的数不是 number，替换
                map.put(index, number);
                indexMap.get(num).remove(index);
                PriorityQueue<Integer> p = indexMap.getOrDefault(number, null);
                if (null == p) {
                    p = new PriorityQueue<>(Integer::compareTo);
                    p.add(index);
                    indexMap.put(number, p);
                } else {
                    p.add(index);
                }
            }
        }

        public int find(int number) {
            PriorityQueue<Integer> pq = indexMap.getOrDefault(number, null);
            if (pq == null || pq.size() < 1) {
                return -1;
            } else {
                return pq.peek();
            }
        }
    }


    // TME
    class FoodRatings1 {
        // 存储 烹饪方式下的所有食物
        private Map<String, List<String>> cuisinesFood = new HashMap<>(16);
        // 存储 食物对应的 评分
        private Map<String, Integer> foodRate = new HashMap<>(16);

        public FoodRatings1(String[] foods, String[] cuisines, int[] ratings) {
            if (foods == null || foods.length < 1) {
                return;
            }
            int n = foods.length;
            for (int i = 0; i < n; i++) {
                foodRate.put(foods[i], ratings[i]);
                List<String> list = cuisinesFood.getOrDefault(foods[i], null);
                if (list == null) {
                    list = new ArrayList<>();
                    list.add(foods[i]);
                    cuisinesFood.put(cuisines[i], list);
                } else {
                    list.add(foods[i]);
                }
            }
        }

        public void changeRating(String food, int newRating) {
            foodRate.put(food, newRating);
        }

        public String highestRated(String cuisine) {
            List<String> list = cuisinesFood.getOrDefault(cuisine, null);
            if (list == null || list.size() < 1) {
                return null;
            } else if (list.size() == 1) {
                return list.get(0);
            } else {
                int n = list.size();
                String res = "";
                int r = -1;
                for (String t : list) {
                    Integer nr = foodRate.getOrDefault(t, null);
                    if (nr != null) {
                        if (nr > r || (nr == r && res.compareTo(t) > 0)) {
                            res = t;
                        }
                    }
                }
                return res;
            }
        }
    }

    /**
     * Your FoodRatings object will be instantiated and called as such:
     * FoodRatings obj = new FoodRatings(foods, cuisines, ratings);
     * obj.changeRating(food,newRating);
     * String param_2 = obj.highestRated(cuisine);
     */
    class FoodRatings {
        // 烹饪方式对应的食物集合
        HashMap<String, TreeSet<Food>> cuisineFoodMap;
        //食物名字对应的烹饪方式
        HashMap<String, String> foodCuisineMap;
        //食物名字对应的食物对象
        HashMap<String, Food> foodObjMap;

        public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
            cuisineFoodMap = new HashMap<>();
            foodCuisineMap = new HashMap<>();
            foodObjMap = new HashMap<>();

            if (foods == null || foods.length < 1) {
                return;
            }

            for (int i = 0; i < foods.length; i++) {
                String foodName = foods[i];
                String cuisine = cuisines[i];
                int rating = ratings[i];

                Food food = new Food(foodName, rating);
                foodObjMap.put(foodName, food);
                foodCuisineMap.put(foodName, cuisine);

                TreeSet<Food> foodSet = cuisineFoodMap.getOrDefault(cuisine, null);
                if (null == foodSet) {
                    foodSet = new TreeSet<>((o1, o2) -> {
                        if (o1.rating != o2.rating)
                            return o2.rating - o1.rating;
                        else
                            return o1.name.compareTo(o2.name);
                    });
                    foodSet.add(food);
                    cuisineFoodMap.put(cuisine, foodSet);
                } else {
                    foodSet.add(food);
                }
            }
        }

        public void changeRating(String food, int newRating) {
            // 获取当前食物的对象
            Food obj = foodObjMap.getOrDefault(food, null);
            if (obj != null) {
                // 获取当前食物的烹饪方式
                String cuisines = foodCuisineMap.getOrDefault(food, null);
                if (cuisines != null) {
                    // 同一烹饪方式下的食物对象集合
                    TreeSet<Food> foodSet = cuisineFoodMap.getOrDefault(cuisines, null);
                    if (foodSet != null) {
                        // 先移除原来的评分的食物对象
                        foodSet.remove(obj);
                        // 添加新的评分的食物对象，触发重新排序
                        Food newFood = new Food(food, newRating);
                        foodSet.add(newFood);
                        // 添加食物对象映射
                        foodObjMap.put(food, newFood);
                    }
                }
            }
        }

        public String highestRated(String cuisine) {
            TreeSet<Food> foodSet = cuisineFoodMap.get(cuisine);
            if (foodSet == null || foodSet.size() < 1)
                return null;
            return foodSet.first().name;
        }

        class Food {
            String name;
            int rating;

            public Food(String name, int rating) {
                this.name = name;
                this.rating = rating;
            }
        }
    }


    /**
     * Definition for a binary tree node.
     */
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * Your CBTInserter object will be instantiated and called as such:
     * CBTInserter obj = new CBTInserter(root);
     * int param_1 = obj.insert(val);
     * TreeNode param_2 = obj.get_root();
     */
    class CBTInserter {
        private TreeNode root;
        List<TreeNode> list = new ArrayList<>();

        public CBTInserter(TreeNode root) {
            this.root = root;

            if (root == null) return;

            Queue<TreeNode> que = new LinkedList<>();
            que.offer(root);
            TreeNode node;
            while (!que.isEmpty()) {
                node = que.poll();
                list.add(node);
                if (root.left != null) {
                    que.offer(root.left);
                    if (root.right != null) que.offer(root.right);
                }
            }
        }

        public int insert(int val) {
            TreeNode newNode = new TreeNode(val);
            if (list.size() > 0) {
                int k = list.size() - 1;
                TreeNode parent = list.get(k / 2);
                val = parent.val;
                if (k % 2 == 0) parent.left = newNode;
                else parent.right = newNode;
            } else {
                root = newNode;
            }
            list.add(newNode);
            return val;
        }

        public TreeNode get_root() {
            return root;
        }
    }


    /**
     * Your Skiplist object will be instantiated and called as such:
     * Skiplist obj = new Skiplist();
     * boolean param_1 = obj.search(target);
     * obj.add(num);
     * boolean param_3 = obj.erase(num);
     */
    class Skiplist01 {

        // 小顶堆
//        private List<Integer> list;
//        int cnt;
        PriorityQueue<Integer> que;
        public Skiplist01() {
            que = new PriorityQueue<>(Integer::compareTo);
        }

        public boolean search(int target) {
            return que.contains(target);
        }

        public void add(int num) {
            que.add(num);
        }

        public boolean erase(int num) {
            return que.remove(num);
        }
    }

    class Skiplist {
        static final int MAX_LEVEL = 32;
        static final double P_FACTOR = 0.25;
        private final SkiplistNode head;
        private int level;
        private final Random random;

        public Skiplist() {
            this.head = new SkiplistNode(-1, MAX_LEVEL);
            this.level = 0;
            this.random = new Random();
        }

        public boolean search(int target) {
            SkiplistNode curr = this.head;
            for (int i = level - 1; i >= 0; i--) {
                /* 找到第 i 层小于且最接近 target 的元素*/
                while (curr.forward[i] != null && curr.forward[i].val < target) {
                    curr = curr.forward[i];
                }
            }
            curr = curr.forward[0];
            /* 检测当前元素的值是否等于 target */
            if (curr != null && curr.val == target) {
                return true;
            }
            return false;
        }

        public void add(int num) {
            SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
            Arrays.fill(update, head);
            SkiplistNode curr = this.head;
            for (int i = level - 1; i >= 0; i--) {
                /* 找到第 i 层小于且最接近 num 的元素*/
                while (curr.forward[i] != null && curr.forward[i].val < num) {
                    curr = curr.forward[i];
                }
                update[i] = curr;
            }
            int lv = randomLevel();
            level = Math.max(level, lv);
            SkiplistNode newNode = new SkiplistNode(num, lv);
            for (int i = 0; i < lv; i++) {
                /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
                newNode.forward[i] = update[i].forward[i];
                update[i].forward[i] = newNode;
            }
        }

        public boolean erase(int num) {
            SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
            SkiplistNode curr = this.head;
            for (int i = level - 1; i >= 0; i--) {
                /* 找到第 i 层小于且最接近 num 的元素*/
                while (curr.forward[i] != null && curr.forward[i].val < num) {
                    curr = curr.forward[i];
                }
                update[i] = curr;
            }
            curr = curr.forward[0];
            /* 如果值不存在则返回 false */
            if (curr == null || curr.val != num) {
                return false;
            }
            for (int i = 0; i < level; i++) {
                if (update[i].forward[i] != curr) {
                    break;
                }
                /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
                update[i].forward[i] = curr.forward[i];
            }
            /* 更新当前的 level */
            while (level > 1 && head.forward[level - 1] == null) {
                level--;
            }
            return true;
        }

        private int randomLevel() {
            int lv = 1;
            /* 随机生成 lv */
            while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
                lv++;
            }
            return lv;
        }
    }

    class SkiplistNode {
        int val;
        SkiplistNode[] forward;

        public SkiplistNode(int val, int maxLevel) {
            this.val = val;
            this.forward = new SkiplistNode[maxLevel];
        }
    }
}
